﻿#define _CRT_SECURE_NO_WARNINGS 1
#include<stdio.h>
#include<stdlib.h>
#include<math.h>
#include<stdbool.h>
#include<string.h>
#include<stdio.h>
#include<stdlib.h>
#include<stdbool.h>
#include <stdio.h>
#include <stdlib.h>
#include<stdbool.h>
#include<assert.h>
//typedef struct student
//{
//	int num;
//	char name[20];
//}STDatatype;
//typedef int STDatatype;

typedef struct BinaryTreeNode* STDatatype;
typedef struct stack//ֶ֧̬ 
{
    STDatatype* stus;
    int top;//ջ 
    int size;// 
} stack;
void stackInit(stack* ps);
bool Fullstack(stack* ps);
void stackPush(stack* ps, STDatatype x);
void stackPop(stack* ps, STDatatype* x);
void printTop(stack* ps, STDatatype* x);
STDatatype StackTop(stack* ps);
int StackSize(stack* ps);
void StackDestroy(stack* ps);
typedef int BTDataType;

typedef struct BinaryTreeNode
{
    BTDataType _data;
    struct BinaryTreeNode* _left;
    struct BinaryTreeNode* _right;
}BTNode;
typedef struct BinaryTreeNode* Datatype;
#define MAX_SIZE 10
typedef struct
{
    Datatype arr[MAX_SIZE];
    int front;
    int rear;
    int tag;
}SqQueue;
void InitQueue(SqQueue* Q);
bool EmptyQueue(SqQueue* Q);
int InQueue(SqQueue* Q, Datatype x);
int DeQueue(SqQueue* Q, Datatype* x);
bool MeDiumQueue(SqQueue* Q);
int GetFront(SqQueue* Q, Datatype* x);
void ShowQueue(SqQueue* Q);

// 通过前序遍历的数组"ABD##E#H##CF##G##"构建二叉树
BTNode* BinaryTreeCreate(BTDataType* a, int n, int* pi);
// 二叉树销毁
void BinaryTreeDestory(BTNode** root);
// 二叉树节点个数
int BinaryTreeSize(BTNode* root);
// 二叉树叶子节点个数
int BinaryTreeLeafSize(BTNode* root);
// 二叉树第k层节点个数
int BinaryTreeLevelKSize(BTNode* root, int k);
// 二叉树查找值为x的节点
BTNode* BinaryTreeFind(BTNode* root, BTDataType x);
// 二叉树前序遍历 
void BinaryTreePrevOrder(BTNode* root);
// 二叉树中序遍历
void BinaryTreeInOrder(BTNode* root);
// 二叉树后序遍历
void BinaryTreePostOrder(BTNode* root);
// 层序遍历
void BinaryTreeLevelOrder(BTNode* root);
// 判断二叉树是否是完全二叉树
bool BinaryTreeComplete(BTNode* root);
int maxDepth(BTNode* root);
bool isSymmetric(BTNode* root);
//翻转二叉树
BTNode* invertTree(BTNode* root);
//由前序和中序遍历结果还原二叉树
BTNode* BinaryTreeCreate02(BTDataType* f, BTDataType* in, int len);
//使用非递归形式中序遍历二叉树
void BinaryTreeInOrder02(BTNode* root);
#define _CRT_SECURE_NO_WARNINGS 1

void InitQueue(SqQueue* Q)
{
    Q->front = Q->rear = Q->tag = 0;
}
bool MeDiumQueue(SqQueue* Q)
{
    if (Q->front == Q->rear && Q->tag == 1)
    {
        return true;
    }
    else
    {
        return false;
    }
}
bool EmptyQueue(SqQueue* Q)
{
    if (Q->front == Q->rear && Q->tag == 0)
    {
        return true;
    }
    else
    {
        return false;
    }
}
int InQueue(SqQueue* Q, Datatype x)
{
    if (MeDiumQueue(Q))
    {
        printf("队列已满,无法插入\n");
        return 0;
    }
    else
    {
        Q->rear = (Q->rear + 1) % MAX_SIZE;
        Q->arr[Q->rear] = x;
        if (Q->rear == Q->front)
        {
            Q->tag = 1;
        }
        return 1;
    }
}

int DeQueue(SqQueue* Q, Datatype* x)
{
    if (EmptyQueue(Q))
    {
        printf("队列已空，无法删除\n");
        return 0;
    }
    else
    {

        Q->front = (Q->front + 1) % MAX_SIZE;
        *x = Q->arr[Q->front];
        if (Q->front == Q->rear)
        {
            Q->tag = 0;
        }
        return 1;
    }
}
int GetFront(SqQueue* Q, Datatype* x)
{
    if (EmptyQueue(Q))
    {
        printf("队空，无法查看头元素\n");
        return 0;
    }
    *x = Q->arr[(Q->front + 1) % MAX_SIZE];
    return 1;
}
void ShowQueue(SqQueue* Q)
{
    if (EmptyQueue(Q))
    {
        printf("队空，无法展示队列\n");
        return;
    }
    else
    {
        int i = Q->front + 1;
        printf("队列从头到尾展示为：");
        while (i != Q->rear)
        {
            printf("%d ", Q->arr[i]);
            i = (i + 1) % MAX_SIZE;
        }
        printf("%d", Q->arr[i]);
        printf("\n");
    }
}

void stackInit(stack* ps)
{
    ps->top = ps->size = 0;
    ps->stus = NULL;
}
bool Fullstack(stack* ps)
{

    if (ps->top == ps->size)
    {
        return true;
    }
    else
    {
        return false;
    }
}
void stackPush(stack* ps, STDatatype x)
{

    if (Fullstack(ps))
    {

        int newsize = (ps->size == 0) ? 4 : 2 * ps->size;

        STDatatype* newstus = (STDatatype*)realloc(ps->stus, sizeof(STDatatype) * newsize);
        if (newstus == NULL)
        {

            assert(newstus);
        }
        else
        {

            ps->stus = newstus;//扩容成功 
            ps->size = newsize;
        }
    }
    ps->stus[ps->top++] = x;
}
void printTop(stack* ps)
{
    printf("此时栈顶元素为:%d \n", ps->stus[ps->top - 1]);
}
void stackPop(stack* ps, STDatatype* x)
{
    *x = ps->stus[ps->top - 1];
    ps->top--;
}
STDatatype StackTop(stack* ps)
{
    return ps->stus[ps->top - 1];
}
int StackSize(stack* ps)
{
    return ps->top;
}
void StackDestroy(stack* ps)
{
    ps->size = 0;
    free(ps->stus);
    ps->top = 0;
}
#define _CRT_SECURE_NO_WARNINGS 1

BTNode* BinaryTreeCreate(BTDataType* a, int n, int* pi)//前序遍历建二叉树
{

    BTNode* root = (BTNode*)malloc(sizeof(BTNode));

    if (a[*pi] == '#')
    {
        *pi = *pi + 1;
        return NULL;
    }
    root->_data = a[*pi];
    *pi = *pi + 1;
    BTNode* left = (BinaryTreeCreate(a, n, pi));
    BTNode* right = (BinaryTreeCreate(a, n, pi));
    root->_left = left;
    root->_right = right;
    return root;
}
//由前序和中序遍历结果还原二叉树
BTNode* BinaryTreeCreate02(BTDataType* f, BTDataType* in, int len)
{
    if (len <= 0)
    {
        return NULL;
    }
    BTNode* root = (BTNode*)malloc(sizeof(BTNode));
    BTDataType* p = in;
    while (*f != *p)
    {
        p++;
    }
    int n = p - in;
    root->_data = *f;
    root->_left = BinaryTreeCreate02(f + 1, in, n);
    root->_right = BinaryTreeCreate02(f + 1 + n, in + 1 + n, len - n - 1);
    return root;
}
void BinaryTreeInOrder(BTNode* root)
{
    if (root == NULL)
    {
        return;
    }
    else
    {
        BinaryTreeInOrder(root->_left);
        printf("%c ", root->_data);
        BinaryTreeInOrder(root->_right);
    }
}
//使用非递归形式中序遍历二叉树
void BinaryTreeInOrder02(BTNode* node)
{
    stack ST;
    stackInit(&ST);
    BTNode* root = node;
    stackPush(&ST, root);
    BTNode* curnode = (BTNode*)malloc(sizeof(BTNode));

    while (root || StackSize(&ST) != 0)
    {
        if (root)
        {
            stackPush(&ST, root);
            root = root->_left;
        }
        else
        {
            stackPop(&ST, &curnode);
            printf("%c ", curnode->_data);
            root = curnode->_right;
        }

    }
}
void BinaryTreeDestory(BTNode** root)
{
    if (root == NULL || *root == NULL)
    {
        return;
    }
    BTNode* rroot = *root;
    BinaryTreeDestory(&(rroot->_left));
    BinaryTreeDestory(&(rroot->_right));
    free(*root);

}
int BinaryTreeSize(BTNode* root)
{
    if (root == NULL)
    {
        return 0;
    }
    else
    {
        return BinaryTreeSize(root->_left) + BinaryTreeSize(root->_right) + 1;
    }
}
int BinaryTreeLeafSize(BTNode* root)
{
    if (root->_left == NULL && root->_right == NULL)
    {
        return 1;
    }
    else if (root->_left == NULL && root->_right != NULL)
    {
        return BinaryTreeLeafSize(root->_right);
    }
    else if (root->_left != NULL && root->_right == NULL)
    {
        return BinaryTreeLeafSize(root->_left);
    }
    else
    {
        return BinaryTreeLeafSize(root->_left) + BinaryTreeLeafSize(root->_right);
    }
}
int BinaryTreeLevelKSize(BTNode* root, int k)
{
    if (k == 1)
    {
        if (root != NULL)
        {
            return 1;
        }
        else return 0;
    }
    else
    {
        if (root != NULL)
        {
            return BinaryTreeLevelKSize(root->_left, k - 1) + BinaryTreeLevelKSize(root->_right, k - 1);
        }
        else
            return 0;
    }
}
BTNode* BinaryTreeFind(BTNode* root, BTDataType x)
{
    if (root == NULL)
    {
        return NULL;
    }
    if (root->_data == x)
    {
        return root;
    }
    else
    {
        BTNode* ret1 = BinaryTreeFind(root->_left, x);
        if (ret1 != NULL)
        {
            return ret1;
        }
        BTNode* ret2 = BinaryTreeFind(root->_right, x);

        if (ret2 != NULL)
        {
            return ret2;
        }

        return NULL;

    }

}
void BinaryTreePrevOrder(BTNode* root)
{
    if (root == NULL)
    {
        return;
    }
    printf("%c ", root->_data);


    BinaryTreePrevOrder(root->_left);
    BinaryTreePrevOrder(root->_right);
}
void BinaryTreePostOrder(BTNode* root)
{
    if (root == NULL)
    {
        return;
    }
    BinaryTreePostOrder(root->_left);
    BinaryTreePostOrder(root->_right);
    printf("%c ", root->_data);
}

int maxDepth(BTNode* root) {
    if (root == NULL)
    {
        return 0;
    }
    else
    {
        int left = maxDepth(root->_right);
        int right = maxDepth(root->_right);
        return left > right ? left : right;
    }
}
//int BinaryTreeComplete(BTNode* root)
//{
//    if (pow(2, maxDepth(root)) - 1 == BinaryTreeSize(root))
//    {
//        return 1;
//    }
//    else
//        return 0;
//} 写错了，这个是判断满二叉树，不是判断完全二叉树
bool isSymmetric(BTNode* root) {

    if (root->_right == NULL && root->_left == NULL)
    {
        return true;
    }
    else if (root->_right == NULL && root->_left != NULL)
    {
        return false;
    }
    else if (root->_right != NULL && root->_left == NULL)
    {
        return false;
    }
    else if (root->_left->_data != root->_right->_data)
    {
        return false;
    }
    else
    {
        return isSymmetric(root->_right) && isSymmetric(root->_left);
    }
}


//void _invertTree(BTNode* root, BTNode* root2)
//{
//    if (root == NULL)
//    {
//        BTNode* swap=root2;
//        root2 = root;
//        root = swap;
//        return;
//    }
//    //_invertTree(root->_left, root2->_right);
//    BTNode* swap = root2->_left;
//    root2->_left = root->_right;
//    root->_right = swap;
//   
//    _invertTree(root->_right, root2->_left);
//    _invertTree(root->_left, root2->_right);

//    /*root2=root;
//    if(root==NULL)
//    {
//        return;
//    }
//    _invertTree(root->left,root2->right);
//    _invertTree(root->right,root2->left);*/
//}
 //翻转二叉树
BTNode* invertTree(BTNode* root) {

    if (root == NULL)
    {
        return NULL;
    }
    BTNode* swap = root->_left;
    root->_left = root->_right;
    root->_right = swap;
    invertTree(root->_left);
    invertTree(root->_right);
    return root;
}
void BinaryTreeLevelOrder(BTNode* root)
{
    SqQueue Q;
    InitQueue(&Q);
    InQueue(&Q, root);
    while (!EmptyQueue(&Q))
    {
        Datatype out;
        DeQueue(&Q, &out);
        if (out->_left != NULL)
            InQueue(&Q, out->_left);
        if (out->_right != NULL)
            InQueue(&Q, out->_right);
        printf("%c ", out->_data);
    }
}
bool BinaryTreeComplete(BTNode* root)
{
    SqQueue Q;
    InitQueue(&Q);
    InQueue(&Q, root);
    Datatype out;
    DeQueue(&Q, &out);
    while (out != NULL)
    {
        InQueue(&Q, out->_left);
        InQueue(&Q, out->_right);
        DeQueue(&Q, &out);
    }
    bool flag = true;
    while (!EmptyQueue(&Q))
    {
        DeQueue(&Q, &out);
        if (out != NULL)
        {
            flag = false;
            break;
        }
    }
    return flag;
}
void chuangjian(BTNode* bt,int*arr,int size)
{
    if (size == 0)
    {
        bt->_left = bt->_right = NULL;
        return;
    }
    else if (size == 1)
    {
        int x = arr[size - 1];
        bt->_right = x;
        BTNode* bt3= (BTNode*)malloc(sizeof(BTNode));
        bt->_right = bt3;
        bt->_right->_left = bt->_right->_right = NULL;
        bt->_left = NULL;
    }
    int x = arr[size - 1];
    bt->_data = x;
    BTNode* bt1 = (BTNode*)malloc(sizeof(BTNode));
    BTNode* bt2 = (BTNode*)malloc(sizeof(BTNode));
    bt->_left = bt1;
    bt->_right = bt2;
    chuangjian(bt->_right, arr + size / 2, (size - 1) / 2);
    chuangjian(bt->_left, arr, size / 2);
}
int main()
{
    int n = 0;
    scanf("%d", &n);
    int* arr = (int*)malloc(sizeof(int) * n);
    for (int i = 0; i < n; i++)
    {
        scanf("%d", &arr[i]);
    }
    BTNode* bt = (BTNode*)malloc(sizeof(BTNode));
    chuangjian(bt, arr, n);
    BinaryTreePostOrder(bt);
}